\begin{frame}[allowframebreaks]
\frametitle{Restarting tiling automaton}

The restarting tiling automata does not need such a restricted definition of scanning strategies. Therefore, we need another definition. 

\begin{define}[Scanning strategy \cite{conf/wia/PrusaM12}]
	A scanning strategy is a tuple $v = (c_s, f)$, where
	\begin{itemize}
		\item $c_s$ is a starting corner, $c_s \in \{1, 2, 3, 4\}$ for the tl, tr, br, bl corner respectively. 
		\item $f: \mathbb{N}^4 \rightarrow \mathbb{N}^2$, where $(i, j, m, n)$ is the next scanned position after $(i, j)$ of pictures with size $(m, n)$. 
	\end{itemize}
	The sequence of visited positions $(i_0, j_0), (i_1, j_1), \dots, (i_{(m+1)(n+1)-1}, j_{(m+1)(n+1)-1})$ is a permutation of the set of $\hat{P}(m, n)$. 
\end{define}

\begin{Example}
	$v_{row} = (1, \mathfrak{s}_{row})$. 
\end{Example}

\begin{define}[Two dimensional restarting tiling automaton (2RTA) \cite{conf/wia/PrusaM12}]
	$M = (\Sigma, \Gamma, \Theta_f, \delta, v, \mu)$ is a two dimensional restarting tiling automaton, where
	\begin{itemize}
		\item $\Sigma$ is a finite input alphabet
		\item $\Gamma$ is a finite working alphabet $(\Sigma \subseteq \Gamma)$
		\item $\Theta_f \subseteq (\Gamma \cup \Sigma)^{2,2}$ is a set of accepting tiles
		\item $v = (c_s, f)$ is a scanning strategy
		\item $\mu: \Gamma \rightarrow \mathbb{N}$ is a weight function. 
		\item $\delta \subseteq \{(u \rightarrow v) \mid u, v \in (\Gamma \cup \{\#\})^{2,2}\}$ is a set of rewriting rules, where for each rule $u \rightarrow v$ only a single position of u, containting a symbol $a \in \Gamma$ is changed to some $b \in \Gamma$ such that $\mu(b) < \mu(a)$. 
	\end{itemize}
\end{define}

The automaton works as follows: 

\begin{itemize}
	\item M scans the picture with a window of size $(2, 2)$ according to the scanning strategy. 
	\item If M finds a position, where a rewrite rule can be applied, one of the possible rewrites is selected. The automaton restarts afterwards. 
	\item If no rewrite rule can be applied to the whole picture, then automaton checks, if the picture belongs to $L(\Theta_f)$. If the picture belongs to $L(\Theta_f)$, the automaton accepts, otherwise rejects. 
\end{itemize}

\pagebreak

We write: 

\begin{itemize}
	\item $P_1 \vdash_M P_2$, if $P_2$ is created from $P_1$ in M by one rewrite step and restart afterwards. 
	\item $P_1 \vdash_M^* P_2$ is the reflexive, transitive closure of $\vdash$. 
\end{itemize}

\begin{define}
	If M is a restarting tiling automaton, the language generated by M is: 
	
	$L(M) = \{p \in \Sigma^{**} \mid \exists q \in \Gamma^{**}: p \vdash_M^* q \text{ and } q \in L(\Theta_f)\}$
\end{define}

\begin{define}[Deterministic restarting tiling automaton (2DRTA) \cite{conf/wia/PrusaM12}]
	A two-dimensional restarting automaton is called deterministic, if for every rule $u \rightarrow v$, there exists no rule $u \rightarrow v'$ for some $v' \neq v$. 
\end{define}

\begin{Example}
	$M = (\{a\}, \{a, 1\}, \Theta_f, \delta, v, \mu)$ with
	\begin{itemize}
		\item $\Theta_f$ $\hat{=}$ tiles, which allow square pictures of a's, which 1's at the diagonal.
		\item \[\delta = \left\{\begin{tabular}{|c|c|}
					\hline
					\# & \# \\
					\hline
					\# & a \\
					\hline					
				\end{tabular} \rightarrow \begin{tabular}{|c|c|}
					\hline
					\# & \# \\
					\hline
					\# & 1 \\
					\hline					
				\end{tabular}, \begin{tabular}{|c|c|}
					\hline
					1 & a \\
					\hline
					a & a \\
					\hline					
				\end{tabular} \rightarrow \begin{tabular}{|c|c|}
					\hline
					1 & a \\
					\hline
					a & 1 \\
					\hline					
				\end{tabular}\right\}\]
		\item $v = v_{row}$
		\item $\mu(a) = 2, \mu(1) = 1$. 
	\end{itemize}
\end{Example}

Then $L(M) = \{p \in \{a\} \mid l_1(p) = l_2(p)\}$ is the language, containing only square words of $a's$. 

\begin{thm}
	For each scanning straegy $v$, $\mathcal{L}(v-2RTA)$ is closed under projection. 
\end{thm}

\begin{proof}
	Let $\varphi: \Sigma_1 \rightarrow \Sigma_2$ be a projection. We want to show, that, if $L_1 \subseteq \Sigma_1$ can be accepted by a $v-2RTA$, then $L_2 = \varphi(L_1)$ is also accepted by an $v-2RTA$. 
	
	Idea: Use rewriting rules, to ''reverse'' the projection (details in \cite{conf/wia/PrusaM12}).
\end{proof}

\pagebreak

\begin{thm}
	For any scanning strategy $v$, $\mathcal{L}(v-2RTA)$ is closed under union and intersection. 
\end{thm}

\begin{proof}
	Idea: Replace any symbol x in the input picture by $(x, x)$ and simulate both automaton on each symbol. 
\end{proof}

\begin{define}[Strategy independant restarting tiling automaton \cite{conf/wia/PrusaM12}]
	If a language is accepted by any 2RTA, independant of the scanning strategy, we call the languages strategy independant. The class of languages generated is $si-2RTL$. Similar for $si-2DRTL$. 
\end{define}

\begin{col}
	$si-2RTL$ and $si-2DRTL$ are closed projection, under union and intersection. 
\end{col}
	
\begin{thm}
	$si-2RTL$ and $si-2DRTL$ are closed under verical and horizontal mirroring and rotation. 
\end{thm}

\begin{proof}
	Idea: Mirror (rotate) the rules and modify the given scanning strategy (details in \cite{conf/wia/PrusaM12}). 
\end{proof}

\begin{thm}
	Let $v$ be a scanning strategy, which always ends in the same corner for any picture. Then $\mathcal{L}(v-2DRTA)$ is closed under complement. 
\end{thm}

\begin{proof}
	Idea: Construct another v-2DRTA and after using rules from the orginal one, mark wheter a tile belongs to $\Theta_f$ or not. Tiles, which are marked to not belong to $\Theta_f$ spread this marker over the whole picture. The local language must then only contain tiles, which are marked to not belong to $\Theta_f$. (details see \cite{pruvsa2012new}).
\end{proof}

We do not know, wheter $si-2RTL$ is closed under column and row concatenations. 

\begin{thm}
	$\mathcal{L}(si-2RTA) \subseteq REC \subseteq \mathcal{L}(2RTA)$
\end{thm}

\begin{proof}
	See \cite{conf/wia/PrusaM12}
\end{proof}

\begin{thm}
	$DREC \subseteq \mathcal{L}(2DRTA)$
\end{thm}

\begin{proof}
	See \cite{pruvsa2012new}
\end{proof}

\end{frame}

\begin{frame}[allowframebreaks]
\frametitle{2RTA over One-Row Picture}

To get an idea of the strength of 2RTA's, we will take a look on 2RTA's working on strings. 

\begin{thm}
	It exists a 2DRTA, which accepts a language $L \subseteq \Sigma^*$, which is not regular. 
\end{thm}

\begin{thm}
	$\mathcal{L}(v_{row}-2RTA)$ and $si-2RTL$ restricted to one dimensional picture languages are equal to the class of regular string languages. 
\end{thm}

\end{frame}